package heap;

import java.util.Random;

import array.CandyArray;

/**
 * 
 * @Title: CandyMaxHeap.java 
 * @Package heap 
 * @Description: 自定义一个最大堆，基于数组实现
 * @author CandyWall   
 * @date 2021年1月8日 下午3:06:22 
 * @version V1.0
 */
public class CandyMaxHeap<E extends Comparable<E>> {
    private CandyArray<E> data;
    
    public CandyMaxHeap(int capacity) {
        data = new CandyArray(capacity);
    }
    
    public CandyMaxHeap() {
        data = new CandyArray();
    }
    
    // 传入一个数组，将数组调整成一个最大堆
    public CandyMaxHeap(E[] arr) {
        data = new CandyArray(arr);
        for(int i = getParentIndex(data.getSize()); i >= 0; i--) {
            shiftDown(i);
        }
    }
    
    // 返回堆中的元素个数
    public int getSize() {
        return data.getSize();
    }
    
    // 堆是否为空
    public boolean isEmpty() {
        return data.isEmpty();
    }
    
    // 在完全二叉树的数组表示中，根据子节点的索引获取父节点的索引
    private int getParentIndex(int childIndex) {
        if(childIndex == 0) {
            throw new IllegalArgumentException("根节点是没有父节点的");
        }
        return (childIndex - 1) / 2;
    }
    
    // 在完全二叉树的数组表示中，根据父节点的索引获取左孩子节点的索引
    private int getLeftChildIndex(int parentIndex) {
        return parentIndex * 2 + 1;
    }
    
    // 在完全二叉树的数组表示中，根据父节点的索引获取右孩子节点的索引
    private int getRightChildIndex(int parentIndex) {
        return parentIndex *2 + 2;
    }
    
    public void add(E e) {
        data.addLast(e);
        shiftUp(data.getSize() - 1);
    }
    
    // 根据新加入的元素，向上调整堆
    private void shiftUp(int childIndex) {
        while(childIndex > 0 && data.get(getParentIndex(childIndex)).compareTo(data.get(childIndex)) < 0) {
            data.swap(getParentIndex(childIndex), childIndex);
            childIndex = getParentIndex(childIndex);
        }
    }
    
    // 获取堆中最大元素，即堆顶元素
    public E getMax() {
        if(data.getSize() == 0) {
            throw new IllegalArgumentException("堆为空，没有元素！");
        }
        return data.get(0);
    }
    
    // 提取堆中最大元素，并将最大元素从堆中移除
    public E extractMax() {
        // 获取堆中最大元素
        E ret = getMax();
        
        // 将最大元素从堆中删除
        // 这里采用堆中最后一个元素和堆顶元素交换，并且删除最后一个元素的方式完成删除
        // data.set(0, data.remove(data.getSize() - 1));
        data.swap(0, data.getSize() - 1);
        data.removeLast();
        shiftDown(0);
        
        return ret;
    }

    public int getCapacity() {
        return data.getCapacity();
    }

    // 根据堆顶的新元素，向下调整堆
    private void shiftDown(int parentIndex) {
        // 左孩子的索引越界，那么表示没有孩子节点了，调整操作结束
        // 反之继续调整堆
        while(getLeftChildIndex(parentIndex) < data.getSize()) {
            // 获取左孩子的索引
            int j = getLeftChildIndex(parentIndex);
            // 如果有右孩子，并且右孩子的值更大，记录右孩子的索引
            if(j + 1 < data.getSize() && data.get(j).compareTo(data.get(j + 1)) < 0) {
                j++;
            }
            // data.get(j) 是 左右孩子中的较大者
            // 如果父节点大于等于子节点，没有违反最大堆的规则，停止调整
            if(data.get(parentIndex).compareTo(data.get(j)) >= 0) {
                break;
            } 
            
            // 如果父节点比子节点小，交换父子节点的值
            data.swap(parentIndex, j);
            parentIndex = j;
        }
    }
    
    // 取出堆中最大的元素，并且替换成元素e
    public E replace(E e) {
        E ret = getMax();
        data.set(0, e);
        return ret;
    }
    
    public static void main(String[] args) {
        int n = 1000_000;
        CandyMaxHeap<Integer> maxHeap = new CandyMaxHeap<>();
        Random random = new Random();
        for(int i = 0; i < n; i++) {
            maxHeap.add(random.nextInt(Integer.MAX_VALUE));
        }
        
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = maxHeap.extractMax();
        }
        
        for(int i = 1; i < n; i++) {
            if(arr[i - 1] < arr[i]) {
                throw new RuntimeException("构建的最大堆有问题！");
            }
        }
        
        System.out.println("最大堆是正确的！");
    }
}
